{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Product of Array Except Self\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/YVOFraWQLvz8cPRHIkwOqg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "You are given an array of integers. Return an array of the same size where the element at each index is the product of all the elements in the original array except for the element at that index.\n",
    "\n",
    "```text\n",
    "Input: [1, 2, 3, 4, 5]\n",
    "Output: [120, 60, 40, 30, 24]\n",
    "```\n",
    "\n",
    "**Note:** *You cannot use division in this porblem.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def products(nums):\n",
    "    ''' Main Algorithm '''\n",
    "    \n",
    "    # Production begins from head.\n",
    "    prefix = []\n",
    "    for elem in nums:\n",
    "        if prefix != []:\n",
    "            prefix.append(prefix[-1] * elem)\n",
    "        else:\n",
    "            prefix.append(elem)\n",
    "    \n",
    "    # Production begins from tail.\n",
    "    suffix = []\n",
    "    for elem in nums[-1::-1]:\n",
    "        if suffix != []:\n",
    "            suffix.append(suffix[-1] * elem)\n",
    "        else:\n",
    "            suffix.append(elem)\n",
    "    suffix = suffix[-1::-1]\n",
    "    \n",
    "    # Generate result.\n",
    "    result = []\n",
    "    for i in range(len(nums)):\n",
    "        if i == 0:\n",
    "            result.append(suffix[i + 1])\n",
    "        elif i == len(nums) - 1:\n",
    "            result.append(prefix[i - 1])\n",
    "        else:\n",
    "            result.append(prefix[i - 1] * suffix[i + 1])\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[120, 60, 40, 30, 24]\n"
     ]
    }
   ],
   "source": [
    "''' Test Scripts '''\n",
    "print(products([1, 2, 3, 4, 5]))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
